package com.hdu.hot100.slideWindow;

import java.util.*;

public class lc438 {
    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            Map<Character, Integer> targetWindow = new HashMap<>() , curWindow = new HashMap<>();
            List<Integer> ans = new ArrayList<>();
            for (char c : p.toCharArray())
            {
                targetWindow.put(c, targetWindow.getOrDefault(c, 0) + 1);
            }
            int curValid = 0, targetValid = 0;
            targetValid = targetWindow.size();
            int l = 0, r = 0;
            while (r < s.length()) {
                char curChar = s.charAt(r);
                curWindow.put(curChar, curWindow.getOrDefault(curChar, 0) + 1);
                if (needChange(targetWindow, curWindow, curChar)) curValid++;
                while (curValid == targetValid)
                {
                    int len = r - l + 1;
                    if (len == p.length())
                    {
                        ans.add(l);
                    }
                    char leftChar = s.charAt(l);
                    if (needChange(targetWindow, curWindow, leftChar)) curValid--;
                    if (curWindow.get(leftChar) == 1) curWindow.remove(leftChar);
                    else curWindow.put(leftChar, curWindow.get(leftChar) - 1);
                    l++;
                }
                r++;
            }
            return ans;
        }

        boolean needChange(Map<Character, Integer> targetWindow, Map<Character, Integer> curWindow, char c)
        {
            return curWindow.get(c).equals(targetWindow.get(c));
        }
    }
}
